import java.util.Stack;

/**
 * 给定一个二叉树，检查它是否是镜像对称的。
 * 进阶：
 * 你可以运用递归和迭代两种方法解决这个问题吗？
 */
class Scratch {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node21 = new TreeNode(2);
        TreeNode node22 = new TreeNode(2);
        TreeNode node31 = new TreeNode(3);
        TreeNode node32 = new TreeNode(3);
        TreeNode node42 = new TreeNode(4);
        root.left = node21;
        root.right = node22;
        node21.right = node31;
        node22.left = node32;
        node22.right = node42;
       /* TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        root.left = node2;
        root.right = node3;*/
        System.out.println(isSymmetric(root));
    }

    /**
     * 用递归
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric1(TreeNode root) {
        return isSymmetric1(root.left, root.right);
    }

    public static boolean isSymmetric1(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return isSymmetric1(node1.left, node2.right) && isSymmetric1(node1.right, node2.left);
    }

    /**
     * 用迭代
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        // 开两个指针，一个从左遍历，一个从右遍历
        TreeNode node1 = root.left;
        TreeNode node2 = root.right;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        while (true) {
            // 如果都不为空
            if (node1 != null && node2 != null) {
                if (node1.val != node2.val) {
                    // 如果两个节点的值不一样
                    return false;
                }
                if ((node1.left != null && node2.right == null)
                        || (node1.left == null && node2.right != null)
                        || (node1.right != null && node2.left == null)
                        || (node1.right == null && node2.left != null)) {
                    // 如果左右有一个为空，有一个不为空
                    return false;
                }
                if (node1.left != null) {
                    stack1.push(node1);
                    stack2.push(node2);
                    node1 = node1.left;
                    node2 = node2.right;
                } else if (node1.right != null) {
                    node1 = node1.right;
                    node2 = node2.left;
                } else {
                    // 如果当前节点的左右节点都是空的
                    if (stack1.isEmpty() && stack2.isEmpty()) {
                        break;
                    }
                    if (stack1.isEmpty() || stack2.isEmpty()) {
                        return false;
                    }
                    node1 = stack1.pop().right;
                    node2 = stack2.pop().left;
                }
            } else if (node1 == null && node2 == null) {
                // 如果两个节点都是空的
                if (stack1.isEmpty() && stack2.isEmpty()) {
                    break;
                }
                if (stack1.isEmpty() || stack2.isEmpty()) {
                    return false;
                }
                node1 = stack1.pop().right;
                node2 = stack2.pop().left;
            } else {
                // 如果有一个为空
                return false;
            }
        }
        return true;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}